import static org.junit.Assert.assertEquals;

import java.util.List;

import org.junit.Test;


public class StringSearchTests {
	//Test Strings
	private final String simpleNeedle = "find me";
	private final String simpleHaystack = "maybe i figure your finder might "
			+ "even find me.";
	
	private final String complexNeedle1 = "aaa";
	private final String complexHaystack1 = "aaaaabb";
	private final String complexNeedle2 = "sea";
	private final String complexHaystack2 = "she sells seashells by the "
			+ "seashore sitting in a seat by the sea.";
	private final String complexNeedle3 = "007";
	private final String complexHaystack3 = "07#008@0()99$90(@_@)1077007 "
			+ "_56007)@_@(006-007!(@@)_!!";
	private final String complexNeedle4 = "(@_@)";
	
	@Test
	public void exampleBoyerMooreTests(){
		String needle = "aardvark";
		//First homework example...
		String haystack1 = "anteaters are aardvarks";
		List<Integer> finds1 = StringSearch.boyerMoore(needle, haystack1);
		
		//Second homework example...
		String haystack2 = "crush kkyle with aardvarks";
		List<Integer> finds2 = StringSearch.boyerMoore(needle, haystack2);
		
		assertEquals(1, finds1.size());
		assertEquals(14, (int)finds1.get(0));
		
		assertEquals(1, finds2.size());
		assertEquals(17, (int)finds2.get(0));
	}
	
	@Test
	public void exampleKMPTest(){
		String needle = "abcdabcabe";
		String haystack = "abcdabcabcdabcfabcdabcabe";
		List<Integer> finds = StringSearch.kmp(needle, haystack);
		
		assertEquals(1, finds.size());
		assertEquals(15, (int)finds.get(0));
	}
	
	@Test
	public void simpleTests() {
		List<Integer> findsBM = StringSearch.boyerMoore(simpleNeedle, simpleHaystack);
		List<Integer> findsKMP = StringSearch.kmp(simpleNeedle, simpleHaystack);
		List<Integer> findsRK = StringSearch.rabinKarp(simpleNeedle, simpleHaystack);
		
		assertEquals(1, findsBM.size());
		assertEquals(38, (int)findsBM.get(0));
		
		assertEquals(1, findsKMP.size());
		assertEquals(38, (int)findsKMP.get(0));
		
		assertEquals(1, findsRK.size());
		assertEquals(38, (int)findsRK.get(0));
	}
	
	@Test
	public void complexBoyerMooreTest(){
		//Repeated letter test...
		List<Integer> findsBM1 = StringSearch.boyerMoore(complexNeedle1, complexHaystack1);
		
		//Repeated word test...
		List<Integer> findsBM2 = StringSearch.boyerMoore(complexNeedle2, complexHaystack2);
		
		//Numbers and symbols test...
		List<Integer> findsBM3 = StringSearch.boyerMoore(complexNeedle3, complexHaystack3);
		List<Integer> findsBM4 = StringSearch.boyerMoore(complexNeedle4, complexHaystack3);

		//Check test 1
		assertEquals(3, findsBM1.size());
		for(int i=0; i<findsBM1.size(); i++)
			assertEquals(i, (int)findsBM1.get(i));
		
		//Check test 2
		assertEquals(4, findsBM2.size());
		assertEquals(10, (int)findsBM2.get(0));
		assertEquals(27, (int)findsBM2.get(1));
		assertEquals(49, (int)findsBM2.get(2));
		assertEquals(61, (int)findsBM2.get(3));
		
		assertEquals(3, findsBM3.size());
		assertEquals(24, (int)findsBM3.get(0));
		assertEquals(31, (int)findsBM3.get(1));
		assertEquals(43, (int)findsBM3.get(2));
		
		assertEquals(1, findsBM4.size());
		assertEquals(15, (int)findsBM4.get(0));
	}
	
	@Test
	public void complexKMPTest(){
		//Repeated letter test...
		List<Integer> findsKMP1 = StringSearch.kmp(complexNeedle1, complexHaystack1);
		
		//Repeated word test...
		List<Integer> findsKMP2 = StringSearch.kmp(complexNeedle2, complexHaystack2);
		
		//Numbers and symbols test...
		List<Integer> findsKMP3 = StringSearch.kmp(complexNeedle3, complexHaystack3);
		List<Integer> findsKMP4 = StringSearch.kmp(complexNeedle4, complexHaystack3);

		//Check test 1		
		assertEquals(3, findsKMP1.size());
		for(int i=0; i<findsKMP1.size(); i++)
			assertEquals(i, (int)findsKMP1.get(i));
		
		//Check test 2
		assertEquals(4, findsKMP2.size());
		assertEquals(10, (int)findsKMP2.get(0));
		assertEquals(27, (int)findsKMP2.get(1));
		assertEquals(49, (int)findsKMP2.get(2));
		assertEquals(61, (int)findsKMP2.get(3));
		
		//Check test 3
		assertEquals(3, findsKMP3.size());
		assertEquals(24, (int)findsKMP3.get(0));
		assertEquals(31, (int)findsKMP3.get(1));
		assertEquals(43, (int)findsKMP3.get(2));
		
		//Check test 4
		assertEquals(1, findsKMP4.size());
		assertEquals(15, (int)findsKMP4.get(0));
	}
	
	@Test
	public void testHashstring(){
		String str = "bunn";
		int hash1 = StringSearch.hashString(str);
		int hash2 = StringSearch.updateHash(StringSearch.hashString("abun"), 'n', 'a', 4);
		
		assertEquals(-1547195621, hash1);
		assertEquals(hash1, hash2);
	}
	
	@Test
	public void complexRabinKarpTest(){
		//Repeated letter test...
		List<Integer> findsRK1 = StringSearch.rabinKarp(complexNeedle1, complexHaystack1);
		
		//Repeated word test...
		List<Integer> findsRK2 = StringSearch.rabinKarp(complexNeedle2, complexHaystack2);
		
		//Numbers and symbols test...
		List<Integer> findsRK3 = StringSearch.rabinKarp(complexNeedle3, complexHaystack3);
		List<Integer> findsRK4 = StringSearch.rabinKarp(complexNeedle4, complexHaystack3);

		//Check test 1		
		assertEquals(3, findsRK1.size());
		for(int i=0; i<findsRK1.size(); i++)
			assertEquals(i, (int)findsRK1.get(i));
		
		//Check test 2
		assertEquals(4, findsRK2.size());
		assertEquals(10, (int)findsRK2.get(0));
		assertEquals(27, (int)findsRK2.get(1));
		assertEquals(49, (int)findsRK2.get(2));
		assertEquals(61, (int)findsRK2.get(3));
		
		//Check test 3
		assertEquals(3, findsRK3.size());
		assertEquals(24, (int)findsRK3.get(0));
		assertEquals(31, (int)findsRK3.get(1));
		assertEquals(43, (int)findsRK3.get(2));
		
		//Check test 4
		assertEquals(1, findsRK4.size());
		assertEquals(15, (int)findsRK4.get(0));
	}
}
